/*
 * =====================================================================================
 *
 *       Filename:  SortProblemLargeTest.cpp
 *
 *    Description:  排序算法对大数据进行测试
 *
 *        Version:  1.0
 *        Created:  2011-10-30 11:34:48
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include "SortProblem.h"
#include <ctime>
#include <iostream>

#define LARGE_COUNT 100000

int clock2milliseconds(const clock_t &start, const clock_t &finish)
{
    return (finish - start) / CLOCKS_PER_SEC * 1000;
}

void runN2Algorithms(void)
{
    clock_t start, finish;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        selectSort(A, 0, A.size() - 1);
        finish = clock();
        std::cout << "selectSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        insertSort(A, 0, A.size() - 1);
        finish = clock();
        std::cout << "insertSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        bubbleSort(A, 0, A.size() - 1);
        finish = clock();
        std::cout << "bubbleSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
}

void runNlgnAlgorithms(void)
{
    clock_t start, finish;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        heapSort(A, 0, A.size() - 1);
        finish = clock();
        std::cout << "heapSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genPositiveRandVector(A, LARGE_COUNT);

        start = clock();
        countSort(A, 0, A.size() - 1, sizeof(int));
        finish = clock();
        std::cout << "countSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }

    std::cout << "quick sort using hoarePartition." << std::endl;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSort(A, 0, (int)A.size() - 1, hoarePartition);
        finish = clock();
        std::cout << "quickSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSortLoop(A, 0, (int)A.size() - 1, &hoarePartition);
        finish = clock();
        std::cout << "quickSortLoop running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSortInsert(A, 0, (int)A.size() - 1, &hoarePartition);
        finish = clock();
        std::cout << "quickSortInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSortMedianOfThreeAndInsert(A, 0, (int)A.size() - 1, &hoarePartition);
        finish = clock();
        std::cout << "quickSortMedianOfThreeAndInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }

    ///////////////////////////////////////////////////////////////
    std::cout << "quick sort using threeWayPartition." << std::endl;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSort(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "quickSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSortLoop(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "quickSortLoop running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSortInsert(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "quickSortInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        quickSortMedianOfThreeAndInsert(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "quickSortMedianOfThreeAndInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }

    //////////////////////////////////////////////////////////////////
    std::cout << "merge sort using mergeOrigin." << std::endl;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSort(A, 0, (int)A.size() - 1, mergeOrigin);
        finish = clock();
        std::cout << "mergeSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithInsert(A, 0, (int)A.size() - 1, mergeOrigin);
        finish = clock();
        std::cout << "mergeSortWithInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoop(A, 0, (int)A.size() - 1, mergeOrigin);
        finish = clock();
        std::cout << "mergeSortLoop running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoopWithInsert(A, 0, (int)A.size() - 1, mergeOrigin);
        finish = clock();
        std::cout << "mergeSortLoopWithInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    //////////////////////////////////////////////////////////////////
    std::cout << "merge sort using mergeUseMax." << std::endl;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSort(A, 0, (int)A.size() - 1, mergeUseMax);
        finish = clock();
        std::cout << "mergeSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithInsert(A, 0, (int)A.size() - 1, mergeUseMax);
        finish = clock();
        std::cout << "mergeSortWithInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoop(A, 0, (int)A.size() - 1, mergeUseMax);
        finish = clock();
        std::cout << "mergeSortLoop running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoopWithInsert(A, 0, (int)A.size() - 1, mergeUseMax);
        finish = clock();
        std::cout << "mergeSortLoopWithInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    //////////////////////////////////////////////////////////////////
    std::cout << "merge sort using mergeExpand." << std::endl;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSort(A, 0, (int)A.size() - 1, mergeExpand);
        finish = clock();
        std::cout << "mergeSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithInsert(A, 0, (int)A.size() - 1, mergeExpand);
        finish = clock();
        std::cout << "mergeSortWithInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoop(A, 0, (int)A.size() - 1, mergeExpand);
        finish = clock();
        std::cout << "mergeSortLoop running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoopWithInsert(A, 0, (int)A.size() - 1, mergeExpand);
        finish = clock();
        std::cout << "mergeSortLoopWithInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    //////////////////////////////////////////////////////////////////
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithCopy(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "mergeSortWithCopy running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithCopyInsert(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "mergeSortWithCopyInsert running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
    {
        std::vector<int> A;
        genPositiveRandVector(A, LARGE_COUNT);

        start = clock();
        mostSignificantDigitSort(A, 0, (int)A.size() - 1);
        finish = clock();
        std::cout << "mostSignificantDigitSort running time is "
                  << clock2milliseconds(start, finish)
                  << " milliseconds"
                  << std::endl;
    }
}

int main(int argc, char *argv[])
{
    enum OPT {OPT_NULL = 0, OPT_ALL, OPT_N2, OPT_NLGN} s_opt;
    static const char *optString = "abch";

    int opt = getopt( argc, argv, optString );

    switch( opt ) {
        case 'a':
            s_opt = OPT_ALL;
            break;

        case 'b':
            s_opt = OPT_N2;
            break;

        case 'c':
            s_opt = OPT_NLGN;
            break;

        case 'h':
            std::cout << "-a show all algorithms.\n"
                      << "-b show n^2 algorithms.\n"
                      << "-c show nlgn algorithms.";
            return 0;
            break;

        default:
            s_opt = OPT_ALL;
            break;
    }

    std::cout << "the max random count is " << LARGE_COUNT << std::endl;

    if (s_opt == OPT_ALL || s_opt == OPT_N2) {
        runN2Algorithms();
    }

    if (s_opt == OPT_ALL || s_opt == OPT_NLGN) {
        runNlgnAlgorithms();
    }
}

